//题目描述
//求 n! 中某个数码出现的次数。
//
//输入格式
//第一行为 t(t≤10)，表示数据组数。接下来 t 行，每行一个正整数 n(n≤1000) 和数码 a。
//
//输出格式
//对于每组数据，输出一个整数，表示 n! 中 a 出现的次数。
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> A, int b)
{
	vector<int> C;
	int t = 0;
	for(size_t i = 0; i < A.size() || t; i++){
		if(i < A.size()) t += A[i] * b;
		C.push_back(t % 10);
		t /= 10;
	}
	while(C.size() > 1 && C.back() == 0) C.pop_back();
	return C;
}
int main()
{
	int t;
	cin >> t;
	while(t--){
		int n, a;
		scanf("%d%d", &n, &a);
		vector<int> A;
		A.push_back(1);
		for(int i = 1; i <= n; i++)
			A = mul(A, i);
		int cnt = 0;;
		for(size_t i = 0; i < A.size(); i++)
			if(A[i] == a) cnt++;
		printf("%d\n", cnt);
	}
	return 0;
}
